1. Field of the Invention
This invention relates to a part arrangement optimizing method which determines the optimum part arrangement under some criterion for evaluation such as a total route length and the like.
2. Description of the Prior Art
FIG. 1 is a flow chart showing a prior art part arrangement optimizing method shown at the 259th page of "DEJITARU KEISANKI NO JIDO SEKKEI (Automated Designing for Digital Computers)," KONPYUTA SAIENSU HONYAKU SENSYO /3 (Translated Selections on Computer Science /3), Mervyn Bloor (ed.), Toshio Ikeda (rev.), Takao Hayashi (trans.), Sangyo Tosho, Tokyo, Oct. 29, 1973 (1st ed.). FIG. 2(a) and FIG. 2(b) are explanatory drawings respectively showing an example of the optimum part arrangement and a non-optimum part arrangement. FIG. 3(a) through FIG. 3(c) are conceptual drawings for explaining interchangeable parts in the part arrangement optimizing method based on the pairwise interchanging method shown in FIG. 1. In FIGS. 2(a) and 2(b), reference numeral 1 designates a part to be arranged in this part arrangement optimizing method; and numeral 3 designates an actual route connecting each part 1 mutually. Also, in FIGS. 3(a) through 3(c), reference numerals 1a, 1b, . . ., 1j designate the same kind of parts as those designated by reference numeral 1 in FIGS. 2(a) , 2(b).
Next, the operation of the prior art part arrangement optimizing method will be described. Hereinafter, the case, where the optimum part arrangement is determined by, for example, the total route length as a criterion for evaluation will be described. For an exercise, a problem which finds the shortest total extension of the route length in the case where the positions of arranged parts and the number of routes among the four parts, which is shown in the following table 1, are given will be considered.
TABLE 1 ______________________________________ PARTS NUMBER 1 2 3 4 ______________________________________ PARTS 1 0 3 3 1 NUMBER 2 3 0 1 3 3 3 1 0 3 4 1 3 3 0 ______________________________________
An example of the optimum solution is shown in FIG. 2(a), and an example of a non-optimum solution by which the total extension of routes is longer than the optimum solution's is shown in FIG. 2(b). There is no analytical solution in such problems as finding the optimum part arrangement, then it is generally required to examine all possible arrangements for finding the optimum solution. However, there are N! combinations of arrangements to N parts, and the time required to the calculation for finding the optimum solution exponetially increases as the part number N increases. Namely, this problem of finding the optimum part arrangement is a kind of the combinational optimization problem. It is usually aimed to find quickly a solution near the optimum solution (or approximate solution) accordingly for solving the problem.
FIG. 1 is a flow chart showing the pairwise interchanging method which is the most basic algorithm among such part arrangement optimizing methods. Although the part arrangement optimizing methods originally deal with the cases where all part sizes are almost the same and all parts can interchange their arranged positions with those of all other parts, hereinafter the part arrangement optimizing method which is improved to be able to deal with problems including different sized parts will be described more generally.
After starting the processes, parts are initially arranged at first (STEP ST1). This initial arrangement of parts may be done randomly, or may be determined so that the total route length becomes somewhat shorter by applying methods such as the pair-linking method, the cluster-developing method, the force placement method or the like. If there are more positions for part arrangement than the total number of parts, vacant areas where any part are not arranged are produced. In that case, dummy parts which are not connected with any other part are arranged at the vacant areas for the time being. And after determining the final part arrangement, the places occupied with the dummy parts are made vacant. Next, a one time cycle is begun (STEP ST2). Then, one part Bi which was not selected at the one time cycle yet is selected (STEP ST3). Therein, the suffix "i", of "B" is made to designate the number of a part. In STEP ST3, dummy parts are not selected. Next, a set of parts {Bj}, the arranged positions of the element parts Bj of which make the total route length shortest by interchanging them with the arranged position of the selected part Bi, is obtained from the set interchangeable with the part Bi (the dummy parts may be included in this case) (STEP ST4).
Now, the set of the parts interchangeable with the part Bi will be described with FIGS. 3(a) through 3(c). Supposing the selected part Bi is the part 1a, the pair of the parts 1d and 1f, the pair of the parts 1d and 1e, and the pair of the parts 1g and 1f are the set interchangeable with the part 1a in case of FIG. 3(a). On the other hand, there is no part set interchangeable with the part la in the case of FIG. 3(b). In the case of FIG. 3(c), too, because the part 1i is different from the part 1a in shape despite being same in size, the part 1i cannot be interchanged with the part 1a, thus there are no part set interchangeable with the part 1a. As mentioned above, the part sets which have the same sizes and shapes as those of the part 1a in case of being combined are the interchangeable part sets.
Next, it is judged whether the total route length becomes shorter or not in case of interchanging the arranged position of the part Bi with that of the part set {Bj} in comparison with the case of non-interchanging (STEP ST5). The arranged positions of the part Bi and the parts set {Bj} are interchanged if the judgement shows that the total route length becomes shorter (STEP ST6), and if the judgement shows that the total route length does not become shorter, the STEP ST 6 is skipped so as not to interchange the part Bi with the parts set {Bj}. Next, it is judged whether all of the parts were selected at the one time cycle or not (STEP ST7). If the result of the judgement shows that there are some parts not selected yet, then the system returns to STEP ST3 and selects the next part among the residual parts except for the dummy parts. On the other hand, if all of the parts have been selected, it is judged whether the reducing rate of the total route length by the one time cycle is smaller than a predetermined value or not (STEP ST8). If the reducing rate is somewhat larger, there is much improving capability in the arrangement, then the system returns to STEP ST2 and begins the next cycle. If the reducing rate is smaller than the predetermined value, the system ends at that place, and finally the part arrangement the total route length of which is reduced is obtained.
Besides, there are other methods such as the relaxation method, a combined method of the relaxation method and the pairwise interchanging method (i.e. the relaxation method according to force directions) and the like as the prior art part arrangement optimizing methods. These methods, too, basically contain steps interchanging or replacing two or more parts and part sets.
Because the prior art part arrangement optimizing methods are constructed as mentioned above, the number of part sets interchangeable with selected part becomes smaller as the kinds of part sizes, especially part shapes, become more, then the capability of interchanging parts decreases as a result of it. Consequently, the prior art methods have problems that they cannot reduce evaluation function values such as the total route length and the like greatly in such cases, and that they cannot obtain good arrangement results which are almost the same as those determined by experts after their long examining.